#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
using namespace std;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        if (N == 1) return 0;
        vector<vector<int>>graph(N + 1);
        for (int i = 1; i <= N; ++i)
            graph[i].resize(N + 1, INT32_MAX);
        for (auto& time : times) 
            graph[time[0]][time[1]] = time[2];
        vector<int>dist(N + 1, INT32_MAX);
        dist[K] = 0;
        vector<bool>visited(N + 1, false);
        while (true) {
            int minIdx = 0;
            for (int i = 1; i < dist.size(); ++i)
                if (!visited[i]&&dist[minIdx] > dist[i])
                    minIdx = i;
            if (minIdx == 0) break;
            visited[minIdx] = true;
            for (int i = 1; i < graph[minIdx].size(); ++i) {
                if (graph[minIdx][i] == INT32_MAX || visited[i])
                    continue;
                dist[i] = min(dist[i], graph[minIdx][i] + dist[minIdx]);
            }
        }
        int cost = 0;
        for (int i = 1; i < dist.size(); ++i) {
            cost = max(cost, dist[i]);
        }
        return cost == INT32_MAX ? -1 : cost;
    }
};

int main() {
    Solution sol;
    vector<vector<int>>tmp = { {1,2,1},{2,3,2},{1,3,4} };
    sol.networkDelayTime(tmp, 3, 1);
}